package org.chargecar.algodev.representativeknn;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Collections;

import org.chargecar.prize.util.PointFeatures;
import org.chargecar.algodev.knn.KdTreeFeatureSet;
import org.chargecar.algodev.knn.KnnPoint;

public class gridTree {
	public class MyException extends Exception {
		/**
		 * 
		 */
		private static final long serialVersionUID = 1L;
		private final String message;

		public MyException(String message) {
			this.message = message;
		}

		public String getMessage() {
			return message;
		}

	};

	private final gridTreeNode root;
	private final int split_x;
	private final int split_y;
	private final int split_z;
	private final double x_max;
	private final double x_min;
	private final double y_max;
	private final double y_min;
	private final double z_max;
	private final double z_min;
	private final double diffMagRate;
	private final double diffNumRate;
	
	private int leafNodeCount;
	private int uncompressedNodeCount;

	public gridTree(List<KnnPoint> points, int split_x, int split_y,
			int split_z, double diffMagRate, double diffNumRate) {
		Collections.sort(points, ComparePowerFlow);
		this.split_x = split_x;
		this.split_y = split_y;
		this.split_z = split_z;
		this.diffMagRate = diffMagRate;
		this.diffNumRate = diffNumRate;
		this.x_max = findMax(points, 0);
		this.x_min = findMin(points, 0);
		this.y_max = findMax(points, 1);
		this.y_min = findMin(points, 1);
		this.z_max = findMax(points, 2);
		this.z_min = findMin(points, 2);
		this.leafNodeCount = 0;
		this.uncompressedNodeCount = points.size() - 2;
		this.root = buildTree(points);
	}
	
	public double getCompressRate() {
		System.out.println("leafNodeCount: " + leafNodeCount);
		System.out.println("uncompressedNodeCount: " + uncompressedNodeCount);
		return (double) uncompressedNodeCount / leafNodeCount;
	}

	public boolean predictable(PointFeatures point) {
		gridLeafNode leafNode = searchTree(root, point);
		if (leafNode == null)
			return false;
		else
			return true;
	}

	public double getBestEstimate(PointFeatures point) throws MyException {
		gridLeafNode leafNode = searchTree(root, point);
		if (leafNode == null)
			throw new MyException("LeafNode is null. Not predictable!");
		return leafNode.getAvePowerFlow();

	}

	public gridLeafNode searchTree(gridTreeNode node, PointFeatures point) {
		if (!inBound(point))
			return null;
		return searchTreeHelper(node, point, x_min, x_max, y_min, y_max, z_min,
				z_max).getNodeValue();
	}

	gridTreeNode searchTreeHelper(gridTreeNode node, final PointFeatures point,
			double x_min, double x_max, double y_min, double y_max,
			double z_min, double z_max) {
		if (node.isLeaf())
			return node;
		else {
			double x_unit = (x_max - x_min) / split_x;
			double y_unit = (y_max - y_min) / split_y;
			double z_unit = (z_max - z_min) / split_z;
			int idx_x = (int) ((getKnnFeatureValue(point, 0) - x_min) / x_unit);
			int idx_y = (int) ((getKnnFeatureValue(point, 1) - y_min) / y_unit);
			int idx_z = (int) ((getKnnFeatureValue(point, 2) - z_min) / z_unit);
			double sub_x_min = x_min + idx_x * x_unit;
			double sub_x_max = sub_x_min + x_unit;
			double sub_y_min = y_min + idx_y * y_unit;
			double sub_y_max = sub_y_min + y_unit;
			double sub_z_min = z_min + idx_z * z_unit;
			double sub_z_max = sub_z_min + z_unit;
			return searchTreeHelper(node.getSubNode(idx_x, idx_y, idx_z),
					point, sub_x_min, sub_x_max, sub_y_min, sub_y_max,
					sub_z_min, sub_z_max);
		}
	}

	private boolean inBound(PointFeatures point) {
		return (getKnnFeatureValue(point, 0) >= x_min
				&& getKnnFeatureValue(point, 0) < x_max
				&& getKnnFeatureValue(point, 1) >= y_min
				&& getKnnFeatureValue(point, 1) < y_max
				&& getKnnFeatureValue(point, 2) >= z_min && getKnnFeatureValue(
				point, 2) < z_max);
	}

	private gridTreeNode buildTree(List<KnnPoint> points) {
		gridTreeNode node = buildTreeHelper(points, x_min, x_max, y_min, y_max,
				z_min, z_max);
		return node;
	}
	
	private gridTreeNode buildGridTreeNode(boolean isLeaf, gridLeafNode leaf) {
		return new gridTreeNode(isLeaf, leaf, split_x, split_y, split_z);
	}

	private gridTreeNode buildTreeHelper(List<KnnPoint> points, double x_min,
			double x_max, double y_min, double y_max, double z_min, double z_max) {
		gridTreeNode node;
		if (points.isEmpty())
			node = buildGridTreeNode(true, null);
		else {
			int min_idx = getMinIdx(points);
			if (checkDiff(points, min_idx)) {
				gridLeafNode leafNode = generateLeaf(points, min_idx);
				node = buildGridTreeNode(true, leafNode);
				leafNodeCount++;
//				System.out.println("Should Be here!!!!!!!!!");
			} else {
				node = buildGridTreeNode(false, null);
				for (int idx_x = 0; idx_x < split_x; idx_x++) {
					for (int idx_y = 0; idx_y < split_y; idx_y++) {
						for (int idx_z = 0; idx_z < split_z; idx_z++) {
							double sub_x_min = x_min + idx_x * (x_max - x_min)
									/ split_x;
							double sub_x_max = sub_x_min + (x_max - x_min)
									/ split_x;
							double sub_y_min = y_min + idx_y * (y_max - y_min)
									/ split_y;
							double sub_y_max = sub_y_min + (y_max - y_min)
									/ split_y;
							double sub_z_min = z_min + idx_z * (z_max - z_min)
									/ split_z;
							double sub_z_max = sub_z_min + (z_max - z_min)
									/ split_z;
							List<KnnPoint> subPoints = pickPoints(points,
									sub_x_min, sub_x_max, sub_y_min, sub_y_max,
									sub_z_min, sub_z_max);
							gridTreeNode tempNode = buildTreeHelper(subPoints,
									sub_x_min, sub_x_max, sub_y_min, sub_y_max,
									sub_z_min, sub_z_max);
							node.setSubNode(tempNode, idx_x, idx_y, idx_z);
						}
					}
				}
			}
		}
		return node;
	}

	static final Comparator<KnnPoint> ComparePowerFlow = new Comparator<KnnPoint>() {
		public int compare(KnnPoint node1, KnnPoint node2) {
			return (node1.getFeatures().getPowerFlow() < node2.getFeatures()
					.getPowerFlow() ? -1
					: (node1.getFeatures().getPeriodMS() == node2.getFeatures()
							.getPowerFlow() ? 0 : 1));
		}
	};

	private int getMinIdx(List<KnnPoint> points) {
		int min_idx = 0;
		// points should be non empty.
		int idx_interval = points.size() - (int) (points.size() * diffNumRate);
		double min_diff = points.get(points.size() - 1).getFeatures()
				.getPowerFlow()
				- points.get(0).getFeatures().getPowerFlow();
		for (int idx = 0; idx < (int) (points.size() * diffNumRate); idx++) {
			double temp_diff = points.get(idx).getFeatures().getPowerFlow()
					- points.get(idx + idx_interval).getFeatures()
							.getPowerFlow();
			if (temp_diff < min_diff) {
				min_diff = temp_diff;
				min_idx = idx;
			}
		}

		return min_idx;
	}

	gridLeafNode generateLeaf(List<KnnPoint> points, int min_idx) {
		double aveLatitude = 0;
		double aveLongtitude = 0;
		double aveBearing = 0;
		double avePowerFlow = 0;
		int idx_interval = points.size() - (int) (points.size() * diffNumRate);
		for (int idx = min_idx; idx < min_idx + idx_interval; idx++) {
			aveLatitude += points.get(idx).getFeatures().getLatitude();
			aveLongtitude += points.get(idx).getFeatures().getLongitude();
			aveBearing += points.get(idx).getFeatures().getBearing();
			avePowerFlow += points.get(idx).getFeatures().getPowerFlow();
		}

		aveLatitude /= points.size();
		aveLongtitude /= points.size();
		aveBearing /= points.size();
		avePowerFlow /= points.size();

		return (new gridLeafNode(new RepresentativeFeatures(aveLatitude,
				aveLongtitude, aveBearing), avePowerFlow, points.size()));
	}

	private boolean checkDiff(List<KnnPoint> points, int idx) {
		int idx_interval = points.size() - (int) (points.size() * diffNumRate);
		double min_diff = points.get(idx + idx_interval - 1).getFeatures().getPowerFlow()
				- points.get(idx).getFeatures().getPowerFlow();
		double max_flow = points.get(idx + idx_interval - 1).getFeatures()
				.getPowerFlow();

		if (min_diff <= max_flow * diffMagRate)
			return true;
		else
			return false;
	}

	private List<KnnPoint> pickPoints(final List<KnnPoint> points,
			double sub_x_min, double sub_x_max, double sub_y_min,
			double sub_y_max, double sub_z_min, double sub_z_max) {
		ArrayList<KnnPoint> subPoints = new ArrayList<KnnPoint>();
		for (KnnPoint point : points) {
			if (getKnnFeatureValue(point, 0) >= sub_x_min
					&& getKnnFeatureValue(point, 0) < sub_x_max
					&& getKnnFeatureValue(point, 1) >= sub_y_min
					&& getKnnFeatureValue(point, 1) < sub_y_max
					&& getKnnFeatureValue(point, 2) >= sub_z_min
					&& getKnnFeatureValue(point, 2) < sub_z_max)
				subPoints.add(point);
		}
		return subPoints;
	}

	private double findMax(List<KnnPoint> points, int field) {
		double max = 0.0;

		for (KnnPoint point : points) {
			if (point != null) {
				double temp = getKnnFeatureValue(point, field);
				if (temp > max)
					max = temp;
			}
		}

		return max;
	}

	private double findMin(List<KnnPoint> points, int field) {
		double min = 0.0;

		for (KnnPoint point : points) {
			if (point != null) {
				double temp = getKnnFeatureValue(point, field);
				if (temp < min)
					min = temp;
			}
		}

		return min;
	}

	private double getKnnFeatureValue(final KnnPoint point, int field) {
		return getKnnFeatureValue(point.getFeatures(), field);
	}

	private double getKnnFeatureValue(final PointFeatures point, int field) {
		switch (field) {
		case 0:
			return point.getLatitude();
		case 1:
			return point.getLongitude();
		case 2:
			return point.getBearing();
		case 3:
			return point.getPowerFlow();

		default:
			System.err.println("Invalid feature request!");
			return 0.0;
		}
	}

}